import random


class SelectionSort:
    """
    选择排序类，包括简单选择排序和堆排序算法的实现。
    """

    @staticmethod
    def selection_sort(arr):
        """
        简单选择排序算法的核心思想是在未排序序列中选择最小（或最大）的元素，将其放到已排序序列的末尾。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：简单选择排序中，元素的选择和交换是基于找到的最小元素的位置，相同元素可能会交换位置，导致相对顺序改变。
        """
        n = len(arr)

        # 步骤 1: 从第一个元素开始，依次选择最小的元素放到已排序序列的末尾
        for i in range(n - 1):
            min_index = i

            # 步骤 2: 在未排序序列中找到最小元素的索引
            for j in range(i + 1, n):
                if arr[j] < arr[min_index]:
                    min_index = j

            # 步骤 3: 将最小元素与当前元素交换位置
            arr[i], arr[min_index] = arr[min_index], arr[i]

        return arr

    @staticmethod
    def heap_sort(arr):
        """
        堆排序算法的核心思想是将待排序的列表构建成一个堆，然后逐步取出堆顶元素，得到排序结果。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        不是稳定排序算法。
        原因：堆排序中，元素的交换和移动是基于堆结构的性质进行的，相同元素可能会交换位置，导致相对顺序改变。
        """
        def heapify(arr, n, i):
            """
            通过将列表调整为最大堆来维护堆结构。

            参数：
            arr (list): 待调整的列表。
            n (int): 列表的长度。
            i (int): 当前节点的索引。

            返回：
            无
            """
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2

            if left < n and arr[left] > arr[largest]:
                largest = left

            if right < n and arr[right] > arr[largest]:
                largest = right

            if largest != i:
                # 步骤 4: 交换节点
                arr[i], arr[largest] = arr[largest], arr[i]
                heapify(arr, n, largest)

        n = len(arr)

        # 步骤 1: 构建最大堆
        for i in range(n // 2 - 1, -1, -1):
            heapify(arr, n, i)

        # 步骤 2: 逐步取出堆顶元素并进行堆调整
        for i in range(n - 1, 0, -1):
            # 步骤 3: 交换堆顶元素与当前元素
            arr[i], arr[0] = arr[0], arr[i]
            heapify(arr, i, 0)

        return arr



# 主程序
if __name__ == "__main__":
    # 生成随机输入列表
    input_list = random.sample(range(1, 101), 10)
    print("随机输入列表:", input_list)

    # 创建 SelectionSort 对象
    sorter = SelectionSort()

    # 调用简单选择排序方法进行排序
    sorted_list_selection = sorter.selection_sort(input_list)
    # 输出结果
    print("简单选择排序后的列表:", sorted_list_selection)  # 简单选择排序后的列表: [1, 2, 4, 5, 7]

    # 调用堆排序方法进行排序
    sorted_list_heap = sorter.heap_sort(input_list)
    # 输出结果
    print("堆排序后的列表:", sorted_list_heap)  # 堆排序后的列表: [1, 2, 4, 5, 7]
